package it.storm.solution;

/**
 * 240. 搜索二维矩阵 II（与 面试题 10.09 同）
 * https://leetcode-cn.com/problems/search-a-2d-matrix-ii/
 */
public class Solutions_240 {
    public static void main(String[] args) {
        int[][] matrix = {{1, 4, 7, 11, 15},
                          {2, 5, 8, 12, 19},
                          {3, 6, 9, 16, 22},
                          {10, 13, 14, 17, 24},
                          {18, 21, 23, 26, 30}};

        int target = 5;  // output: true
//        int target = 20;  // output: false
//        int target = 26;  // output: true

        boolean result = searchMatrix(matrix, target);
        System.out.println(result);
    }


    public static boolean searchMatrix(int[][] matrix, int target) {
        // 利用每行与每列都是升序的特性，把每个元素都想像成二叉搜索树中的根节点
        // 对于该元素，左边的元素一定是比它小的；下面的元素一定是比它大的
        if (matrix == null) {
            return false;
        }
        int row = matrix.length;
        // matrix 为空数组，而 target 有值，则搜索不到 target
        if (row < 1) {
            return false;
        }
        int col = matrix[0].length;
        if (col < 1) {
            return false;
        }
        // target 一定不在矩阵中存在的情况
        if (target < matrix[0][0] || target > matrix[row - 1][col - 1]) {
            return false;
        }
        int x = 0, y = col - 1;
        // 索引合法时，进行查找
        while (x >= 0 && x < row && y >= 0 && y < col) {
            if (target == matrix[x][y]) {
                return true;
            } else if (target < matrix[x][y]) {
                // target 小于当前元素，可能在其左侧
                y --;
            } else {
                // target 大于当前元素，可能在其下方
                x ++;
            }
        }
        return false;
    }
}
